count = 0


def quick_sort(alist, start, end):
    """快速排序"""

    # 递归的结束条件
    if start >= end:
        return
    # print("start: {}, end: {}".format(start, end))
    # 界限值
    mid = alist[start]
    # 左右游标
    left = start
    right = end
    global count
    while left < right:
        # 从右边开始找寻小于mid的值 归类到左边
        while alist[right] >= mid and left < right:
            right -= 1
            count = count + 1
        alist[left] = alist[right]
        alist[right] = mid
        # 从左边开始找寻大于mid的值 归类到右边
        while alist[left] < mid and left < right:
            left += 1
            count = count + 1
        alist[right] = alist[left]
        alist[left] = mid
    # 循环一旦结束了 证明找到了mid应该在的位置
    alist[left] = mid
    # print("count---：{}".format(count))
    # 递归操作
    print("start: {}, end: {} start: {}, end: {}".format(start, left - 1, right + 1, end))
    quick_sort(alist, start, left - 1)
    quick_sort(alist, right + 1, end)


if __name__ == '__main__':
    # alist = [1, 2, 100, 50, 1000, 0, 1, 1]
    # alist = [1, 2, 3, 4, 5, 6, 7]  # 最差快排原始顺序
    alist = [4, 3, 1, 2, 6, 5, 7]  # 应该是最优快排原始顺序
    print(alist)
    quick_sort(alist, 0, len(alist) - 1)
    print("count：{}".format(count))

"""

最差快排：
[1, 2, 3, 4, 5, 6, 7]
start: 0, end: 6  #本层7个数
start: 0, end: -1 start: 1, end: 6 #本层6个数 n-1个数
start: 1, end: 0 start: 2, end: 6 #本层5个数  n-2个数
start: 2, end: 1 start: 3, end: 6 #本层4个数  n-3个数
start: 3, end: 2 start: 4, end: 6 #本层3个数  ...
start: 4, end: 3 start: 5, end: 6 #本层2个数  ...
start: 5, end: 4 start: 6, end: 6 #本层1个数  1个数
count：21                                    共n层，每层的数
最优快排：
[4, 3, 1, 2, 6, 5, 7]
start: 0, end: 6 #本层7个数
start: 0, end: 2 start: 4, end: 6 #本层两部分 3+3个数，即n/2+n/2
start: 0, end: 0 start: 2, end: 2 #本层0个数   数据量小了 ，应该是 n/2/2+n/2/2个数
start: 4, end: 4 start: 6, end: 6 #本层0个数    1   
count：10                                    共log(底数2)n层，每层的数 1*2*2*2...=n n=log(底数2)n  
"""
